The present invention relates to central processing units in computer systems. In particular, it relates to a method and a respective hardware implementation of an add operation and a subtract operation.
Although the present invention has a quite general scope which covers in general method and system for adding and subtracting operands with improved performance and area-optimized implementations it will be next discussed in relation to a specific field of use, namely that of address limit checking. In this particular situation an address A must be checked if it lies within a given zone of the main memory of a computer.
This typical situation is depicted in FIG. 1. Address A is obtained in prior art by adding the base 20 and an offset 22 and comparing the add result, both, with the zone start address 24a and the zone end-address 24b. If address A is within the zone i defined by said start-and end-addresses 24a and b the operation of a program may, for example, be regularly continued and otherwise some prior art exception handling may occur.
Such kind of address limit check operations are often occurred in modern computer systems because the main memory storage size is increased more and more which opens up a variety of operational features, as, for example, to operate on the same central processing unit a first operating system in a first zone and a second operating system in a second memory zone, and loading the respective application programs for being run simultaneously. In such situations most of memory addresses which are issued by any of the executing units must be checked in the above mentioned sense in order to make sure that the application programs may run properly.
In FIG. 1 the memory is partitioned into several zones, indexed by i which is each limited by a start-address and end-address. Thus, multiple zones may be present.
Each zone can begin at a certain xe2x80x98higher levelxe2x80x99 boundary, e.g. 1 Mbyte boundary, and can be expanded up to, e.g., 2 GByte, see FIG. 1. All accesses to a certain zone have then to be checked to stay within the zone. Thus, the more frequent such accesses are the more urgently logic functions are required to efficiently check if address A is greater than zone start (ZS) 24a and if it is smaller than zone end (ZE) 24b. As the address A is generated by adding an offset value to a base register value the complete logical function is a 2-operand add operation followed by an adequate compare operation with the zone boundaries. Said compare operation is usually done by subtracting the zone boundary from the add result. This is a very timing critical path within a computer system as the clock cycle is normally adjusted to a 2-operand addition within the ALU. Thus, in prior art this is done sequentially in time.
Some details concerning said prior art approach are next introduced with reference to FIGS. 2 and 3. For the following discussion and disclosure it is assumed without any restriction that the addresses have a width of 64 bits.
Base address 20 and Offset address 22 (FIG. 1) are byte addresses of 64 bit length, whereas the zone start ZS and zone end ZE usually point to boundaries of e.g. 64 KByte, or even to higher level boundaries as e.g., 1 or 2 Gbyte as mentioned before. The relevant parts of the ZE, ZS addresses are therefore by 16 bits (in case of 64 kByte boundary) shorter. This is illustrated in FIG. 2 where the not relevant part 25 of the zone boundary beyond bit 47 is shown filled with xe2x80x980xe2x80x99 digits (zeros).
In prior art, the above mentioned limit check function was done as it is schematically depicted in FIG. 3, by first adding base and offset with a 2-port adder 30, and second, by performing a greater or smaller compare of bit 0 to bit 47 from the adder result with the value of ZS and ZE, respectively. Therefore, two further, separate logic circuits 32, 34 are used in prior art which begin to work after the add result is present on the output of the 2-port adder 30.
As a person skilled in the art may appreciate two major disadvantages result therefrom:
There is a remarkable performance loss because the compare circuit 32 or 34 have to wait until the add result is present from circuit 30, and
The area consumption required for implementing the compare circuits 32 and 34 is quite large in regard of the quite similar tasks both circuits have to do. Indeed, they are similar in nature because both compare circuits 32, 34 work according to the same principle, i.e. subtracting an operand from another one.
It is thus an object of the present invention to provide a method and system for an improved add and subtract operation.
According to the broadest aspect of the invention a method is provided for performing an add operation with two add operands, and a subtract operation with a third operand, of which a less significant part (25) of its binary (1/0) representation exclusively consists of zeros (0), and the subtract operation involves the result of said add operation. It is characterized by the steps of:
a. preferably using a 2-port adder for adding a less significant part of the add operands the bit length of which corresponds to the respective more significant part of said third operand, for generating a carry-out bit using a first carry network,
b. in a first step of a 3-port operation concurrently to the above step a) adding a respective more significant part 5153 of the add operands for bit wise generating sum bits and carry bits preferably in a full adder stage,
c. in a second step of the 3-port operation performing said subtract operation by bit wise operating a second carry network
with respective bits of the more significant part 55 of said third operand,
with respective ones of said sum bits 56,
with said carry out bit 54 of said less
significant part add operation, and
with the carry-out bits 58 of said more significant part add operation.
Thus, a general approach is disclosed which applications include mathematical add/subtract operations, amongst the address operations which are actually focused by the disclosed concepts.
By the disclosed combination of said add and compare operations a solution is disclosed which is faster than prior art because of the early start of the 3-port subtract operation which can be done before the add operation is completed. Moreover, the 3-port operation and the 2-port add operation is basically started in parallel which accelerates operation.
Further, the timing of the carry-out of the 2-port operation can be adjusted to be active when needed in 3 port operation part:
The carry-out of carrynet 1 takes longer than the fulladder stage of the 3-port operation. Considering FIG. 6, the carry-out of carrynet 1 seems to be needed directly after the sum and carry bits of the 3 port stage are available. Actually, the control bit takes the position of the carry-in. The carry-out of carrynet 1 can then be faced in at the latest possible point of the 2. part of the 3 port operation, FIG. 4. Thus, a lot of parallel work can be done while the carry-out is generated.
Further, when said first and said second operands are base, and offset address operands, and said third operand is a zone start or zone end address of a storage means, and in particular of a physical memory means, which is divided into one or more of said zones, and the disclosed method further comprises the step of evaluating the carry-out of the second carry network for checking if the address given by said add result of add operands is within the address zone defined by said zone start and zone end addresses, then, the particular preferential use of the disclosed method is found, i.e., address arithmetic, and in particular address limit checking is enabled with the third operand being a higher level boundary in memory, e.g., a Megabyte boundary having 20 least significant bits as trailing or leading (architecture-dependent) zeros, respectively. In those cases an efficient address limit checking is provided by the present invention.
When further a control bit is used for distinguishing between a xe2x80x98smaller than or equal toxe2x80x99, or a xe2x80x98greater than or equal toxe2x80x99, (or the respective complementary conditions) compare operation, respectively, then the same implementation can be used for checking both boundaries of a given memory zone, just controlled via said bit which is integrated into the carry part of the second carry network.
Thus, a hardware logic circuit having circuit means for performing the above mentioned disclosed steps may be constructed and used exploiting the advantages cited in here.
Preferably, said control bit is located in the least significant bit position of the location storing the carry bits in the second carry network. This location is usually empty and can thus advantageously be used.
Further, about 30% cell count saving is offered with this approach, and a speed increase of nearly 10% over the cited prior art is achieved.
As a person skilled in the art may appreciate the present invention replaces the sequential steps of prior art by applying more operation parallelism. Thus, a combined logic function for adding and subtracting is provided. This is basically a three-operand operation in which two operands are added and the third one is subtracted during the add. The third operand is basically assumed to be shorter than the two add operands which compose the virtual address, and thus having a certain number of trailing or (leading) xe2x80x980xe2x80x99 (zeros) in its least significant part in order to take profit of all advantages of the disclosed concepts. Otherwisexe2x80x94the third operand having the same size as the other onesxe2x80x94at least the advantage is maintained to save chip area because the combined logic function is smaller than a respective one in prior art.
Thus, the main advantages are that the time is decreased to achieve the result and the amount of circuits needed for the hardware logic implementation is reduced, which reduces chip area consumption. A preferred embodiment of the invention provides one circuit which takes over the task of checking the lower boundary ZS as well as the upper boundary ZE.